package org.example.leetcode.addon.lc108;

import org.example.util.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) return null;

        TreeNode root = new TreeNode(-1);
        Queue<TreeNode> nodes = new LinkedList<>();
        nodes.offer(root);
        Queue<Integer> lefts = new LinkedList<>();
        lefts.offer(0);
        Queue<Integer> rights = new LinkedList<>();
        rights.offer(nums.length - 1);

        while (!nodes.isEmpty()) {
            TreeNode curr = nodes.poll();
            int left = lefts.poll();
            int right = rights.poll();
            int mid = left + ((right - left) / 2);

            curr.val = nums[mid];

            if (left <= mid - 1) {
                curr.left = new TreeNode(-1);
                nodes.offer(curr.left);
                lefts.offer(left);
                rights.offer(mid - 1);
            }

            if (right >= mid + 1) {
                curr.right = new TreeNode(-1);
                nodes.offer(curr.right);
                lefts.offer(mid + 1);
                rights.offer(right);
            }
        }

        return root;
    }
}
